#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define STACKMAXSIZE 50
typedef char StackElemType; 
typedef struct {
	StackElemType elem[STACKMAXSIZE]; 
	int top;
} SeqStack;

void InitSeqStack(SeqStack *S) {
	S->top = -1;
}

int PushStack(SeqStack *S, StackElemType e) {
	if (S->top == STACKMAXSIZE - 1) {
		printf("栈满！\n"); 
		return 0;
	} 
	S->elem[++S->top] = e;
	return 1;
}

int PopStack(SeqStack *S, StackElemType *e) {
	if (S->top == -1) {
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top--];
	return 1;
}

int GetTop(SeqStack *S, StackElemType *e) {
	if (S->top == -1) {
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top];
	return 1;
}

int Prior(char ch) {
	switch(ch) {
		case '+': case '-': return 1;
		case '*': case '/': return 2;
		case '^': return 3;
		case '(': case ')': return 0;
	}
	return -1;
}

int IsOp(char ch) {
	return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' || ch == '(' || ch == ')';
}

int IsDigit(char ch) {
	return ch >= '0' && ch <= '9';
}

void StrToNumber(SeqStack *S, char *str, int *index) {
	int num = 0;
	while (IsDigit(str[*index])) {
		num = num * 10 + (str[*index] - '0');
		(*index)++;
	}
	PushStack(S, num);
}

int ExpEvaluation(char *str) {
	SeqStack opStack, numStack;
	InitSeqStack(&opStack);
	InitSeqStack(&numStack);
	PushStack(&opStack, '#');
	
	int i = 0;
	while (str[i] != '#' || GetTop(&opStack, &StackElemType) != '#') {
		if (IsDigit(str[i])) {
			StrToNumber(&numStack, str, &i);
		} else if (IsOp(str[i])) {
			if (str[i] == '(') {
				PushStack(&opStack, str[i]);
				i++;
			} else if (str[i] == ')') {
				while (GetTop(&opStack, &StackElemType) != '(') {
					int v1, v2, op;
					PopStack(&numStack, &v2);
					PopStack(&numStack, &v1);
					PopStack(&opStack, &op);
					switch (op) {
						case '+': PushStack(&numStack, v1 + v2); break;
						case '-': PushStack(&numStack, v1 - v2); break;
						case '*': PushStack(&numStack, v1 * v2); break;
						case '/': PushStack(&numStack, v1 / v2); break;
						case '^': PushStack(&numStack, (int)pow(v1, v2)); break;
					}
				}
				PopStack(&opStack, &StackElemType); // Pop the '('
				i++;
			} else {
				int opTop;
				while (Prior(str[i]) <= Prior(GetTop(&opStack, &opTop))) {
					int v1, v2, op;
					PopStack(&numStack, &v2);
					PopStack(&numStack, &v1);
					PopStack(&opStack, &op);
					switch (op) {
						case '+': PushStack(&numStack, v1 + v2); break;
						case '-': PushStack(&numStack, v1 - v2); break;
						case '*': PushStack(&numStack, v1 * v2); break;
						case '/': PushStack(&numStack, v1 / v2); break;
						case '^': PushStack(&numStack, (int)pow(v1, v2)); break;
					}
				}
				PushStack(&opStack, str[i]);
				i++;
			}
		} else {
			i++; // Skip invalid characters
		}
	}
	int result;
	PopStack(&numStack, &result);
	return result;
}

int main() 
{
	int v;
	char str[80];
	printf("输入一个表达式，以#为结束！\n");
	gets(str);
	v = ExpEvaluation(str);
	printf("该表达式的运算结果为：%d\n", v);
	return 0; 
}
